package second.codeTop.package1;

import util.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @ClassName LC501
 * @description: 二叉搜索树中的众数
 * @author: 荣燊
 * @create: 2022-03-03 10:24
 **/
public class LC501 {
    public static void main(String[] args) {

    }

    // 维护一个数组，需要定时清理
    static ArrayList<Integer> arrayList = new ArrayList<>();
    // 实时保存 某个数字出现的最大次数
    static int maxCount;
    // 众数
    static int base;
    // 当前的数出现的次数
    static int count;

    // 注意这是二叉搜索树，不是一般的二叉树
    public static int[] findMode(TreeNode root) {
        dfs(root);
        int[] ints = new int[arrayList.size()];
        for (int i=0; i<arrayList.size(); i++) {
            ints[i] = arrayList.get(i);
        }
        return ints;
    }

    // 中序遍历得到的就是有序数组
    public static void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        update(root.val);
        dfs(root.right);
    }

    public static void update(int x) {
        // 如果遍历到的数等于当前的数，就自增出现的次数
        // 否则就重新选择该遍历的数
        if (x == base) {
            ++count;
        } else {
            count = 1;
            base = x;
        }
        // 如果当前的数出现次数大
        if (count == maxCount) {
            arrayList.add(base);
        }
        if (count > maxCount) {
            arrayList.clear();
            arrayList.add(base);
            maxCount = count;
        }

    }
}
